package com.xmg.lru;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class ExecLRU {
    public static void main(String[] args) {
        MyLRU lru = new MyLRU(3);
        lru.put(1,2);
        lru.put(2,3);
        lru.put(3,4);
        lru.put(4,5);
        lru.put(7,8);
        lru.get(4);
        lru.put(1,2);
//        lru.get(2);
        System.out.println(lru.map);
    }
}

class ListLRU<K,V> extends LinkedHashMap{
    int cap;
    public ListLRU(int cap){
        super(cap,0.75f,true);
        this.cap = cap;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return this.size()>cap;
    }
}

class MyLRU{

    static class Node<K,V>{
        K key;
        V value;
        Node next;
        Node prev;
        public Node(K key,V value){
            this.value = value;
            this.key = key;
            this.next = this.prev = null;
        }
        public Node(){
            this.next = this.prev = null;
        }
    }
    static class DoubleLinked<K,V>{
        Node head;
        Node tail;
        public DoubleLinked(){
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
        }

        public void addHead(Node node){
            head.next.prev = node;
            node.next = head.next;
            head.next = node;
            node.prev = head;
        }

        public void remove(Node node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next=null;
            node.prev=null;
        }

        public Node getTail(){
            return tail.prev;
        }
    }

    private int cap;
    HashMap<Integer,Node<Integer,Integer>> map;
    DoubleLinked linked;
    public MyLRU(int cap){
        this.cap = cap;
        map = new HashMap<>(cap);
        linked = new DoubleLinked();
    }

    public int get(int i){
        if(!map.containsKey(i)){
            return -1;
        }
        Node<Integer,Integer> node = map.get(i);
        linked.remove(node);
        linked.addHead(node);
        return node.value;
    }

    public void put(int key,int value){
        if(map.containsKey(key)){
            Node node = map.get(key);
            linked.remove(node);
            linked.addHead(node);
        }else{
            if(map.size()<cap){
                Node<Integer,Integer> node = new Node(key,value);
                map.put(key,node);
                linked.addHead(node);
            }else{
                Node tail = linked.getTail();
                map.remove(tail.key);
                Node node = new Node(key,value);
                map.put(key,node);
                linked.remove(tail);

                linked.addHead(node);
            }
        }
    }

    public HashMap getMap(){
        return map;
    }
}